package uestc.lj.midPromotion.dfs;

/**
 * @Author:Crazlee
 * @Date:2021/12/6
 */
public class Code14_StringToKth {
	/**
	 * 第i个字符开头，长度为len的字符串有多少个
	 *
	 * @param i   开头字符0——a，25——z
	 * @param len 长度
	 * @return 数量
	 */
	public static int g(int i, int len) {
		int sum = 0;
		if (len == 1) {
			return 1;
		}
		for (int j = i + 1; j <= 26; j++) {
			sum += g(j, len - 1);
		}
		return sum;
	}

	/**
	 * 长度为len的字符串有多少个
	 *
	 * @param len
	 * @return
	 */
	public static int f(int len) {
		int sum = 0;
		for (int i = 1; i <= 26; i++) {
			sum += g(i, len);
		}
		return sum;
	}

	public static int kth(String s) {
		char[] str = s.toCharArray();
		int sum = 0;
		int len = s.length();
		//在此之前长度的子序列总数量
		for (int i = 1; i < len; i++) {
			sum += f(i);
		}
		// 以第一个字符开始的之前长度的子序列总数量
		int firstChar = str[0] - 'a' + 1;
		for (int i = 1; i < firstChar; i++) {
			sum += g(i, len);
		}
		int preChar = firstChar;
		for (int i = 1; i < len; i++) {
			int curChar = str[i] - 'a' + 1;
			for (int j = preChar + 1; j < curChar; j++) {
				sum += g(j, len - 1);
			}
			preChar = curChar;
		}
		return sum + 1;
	}
}
